/*
 * BitTools.h
 *
 *  Created on: 03/08/2012
 *      Author: marcio
 */

#ifndef BITTOOLS_H_
#define BITTOOLS_H_

#include <stdlib.h>

/*!
 * \def hum_u a word with 32 bits, all set to 1
 * \def fum_l a word with 64 bits all set to 1
 */
#define hum_u  0xFFFFFFFF
#define hum_l  0xFFFFFFFFFFFFFFF

template<typename T>
class BitTools {

	int 		logw;		//!< logarithmic of the size, in bytes, of a word
	int 		logb;		//!< logarithmic of the size, in bits, of a word
	long 		maskb;		//!< mask used to obtain remainder of division by logb
	int 		word_size;  //!< number of bits of a word

public:

	static const int __masksz;
	static const T __mask[];
	static const unsigned long __nnodesh[8];

	BitTools() {
		logw = inline_ceillog(sizeof(T), 1);
		logb = logw + 3;
		maskb = ~(-1L << logb);
		word_size = 1LL << logb;
		//	printf("n = %ld  logw = %d  logb = %d\n", n, logw, logb);
	};

	/*! \fn inline_ceillog(long n, int b)
	 * \brief Determine the ceil of the logarithmic of the specified value in the specified basis.
	 *
	 * The algorithm is the following: the specified value is successively divided by the specified basis until 1 is obtained.
	 * The number of times the specified gives the floor of the logarithmic. If the remainder of some these divisions is
	 * different from 0, then the floor is incremented by 1 before it is returned.
	 *
	 * \param n the value.
	 * \param b the logarithmic (in basis 2) of the basis.
	 *
	 * \return the ceil of the logarithmic of the specified value in the specified basis.
	 *
	 */
	int inline_ceillog(long n, int b) {
		long c = 0;
		int l = 0;
		while (n >= (1LL << b)) {
			c |= (n & ~(-1 << b));
			n >>= b;
			l++;
		}
		if (c)
			l++;
		return l;
	}

	long quotient(long i) {
		return i >> logb;
	};

	long remainder(long i) {
		return i & maskb;
	};

	/*! \fn builtinCounter(T i)
	 * \brief Builtin function to determine the number of bits 1 in the word i.
	 *
	 * Builtin functions are functions provided to the compiler and depended on the
	 * architecture of the computer to work properly. This kind of function is usually
	 * implemented in hardware level. In order to use this function you have to verify
	 * if the compiler has support to that and if not rewrite this function.
	 *
	 * More documentation about builtin functions can be viewed in
	 *
	 * \sa http://en.wikipedia.org/wiki/C_standard_library
	 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
	 *
	 * \param i the word.
	 * \tparam the type of the word.
	 *
	 * \return the number of bits 1 in i.
	 *
	 */
	static int builtinCounter(T i);

	/*! \fn builtinLeast(T w)
	 * \brief Builtin function to determine the least significant bit 1 in the word i.
	 *
	 * Builtin functions are functions provided to the compiler and depended on the
	 * architecture of the computer to work properly. This kind of function is usually
	 * implemented in hardware level. In order to use this function you have to verify
	 * if the compiler has support to that and if not rewrite this function.
	 *
	 * More documentation about builtin functions can be viewed in
	 *
	 * \sa http://en.wikipedia.org/wiki/C_standard_library
	 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
	 *
	 * \param w the word.
	 * \tparam the type of the word.
	 *
	 * \return the least significant bit 1 in i, if the word has o bit 1 it will return -1.
	 *
	 */
	static int builtinLeast(T w);
	static int builtinNextLeast(T w, int i);


	/*! \fn builtinMost(T i)
	 * \brief Builtin function to determine the most significant bit 1 in the word i
	 *
	 * Builtin functions are functions provided to the compiler and depended on the
	 * architecture of the computer to work properly. This kind of function is usually
	 * implemented in hardware level. In order to use this function you have to verify
	 * if the compiler has support to that and if not rewrite this function.
	 *
	 * More documentation about builtin functions can be viewed in
	 *
	 * \sa http://en.wikipedia.org/wiki/C_standard_library
	 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
	 *
	 * \param i the value.
	 * \tparam the type of the word.
	 *
	 * \return the most significant bit 1 in i, if the word has no bit 1 it will return -1.
	 *
	 */
	static int builtinMost(T i);
	static int builtinNextMost(T w, int i);

};

template<>
const int BitTools<unsigned long long>::__masksz = 65;
template<>
const int BitTools<unsigned long>::__masksz = 33;
template<>
const int BitTools<unsigned int>::__masksz = 17;
template<>
const unsigned int BitTools<unsigned int>::__mask[] =
{
		0xFFFF,
		0xFFFE, 0xFFFC, 0xFFF8, 0xFFF0,
		0xFFE0, 0xFFC0, 0xFF80, 0xFF00,
		0xFE00, 0xFC00, 0xF800, 0xF000,
		0xE000, 0xC000, 0x8000, 0x0000
};
template<>
const unsigned long BitTools<unsigned long>::__mask[] =
{
		0xFFFFFFFF,
		0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, 0xFFFFFFF0,
		0xFFFFFFE0, 0xFFFFFFC0, 0xFFFFFF80, 0xFFFFFF00,
		0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, 0xFFFFF000,
		0xFFFFE000, 0xFFFFC000, 0xFFFF8000, 0xFFFF0000,
		0xFFFE0000, 0xFFFC0000, 0xFFF80000, 0xFFF00000,
		0xFFE00000, 0xFFC00000, 0xFF800000, 0xFF000000,
		0xFE000000, 0xFC000000, 0xF8000000, 0xF0000000,
		0xE0000000, 0xC0000000, 0x80000000, 0x00000000
};
template<>
const unsigned long long BitTools<unsigned long long>::__mask[__masksz] =
{
		0xFFFFFFFFFFFFFFFF,
		0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0,
		0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00,
		0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000,
		0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000,
		0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000,
		0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000,
		0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000,
		0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000,
		0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000,
		0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000,
		0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000,
		0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000,
		0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000,
		0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000,
		0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000,
		0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000
};
template<typename T>
const unsigned long BitTools<T>::__nnodesh[8] =
{
		0x00000000,
		0x00000001, 0x00000021, 0x00000421,	0x00008421,
		0x00108421,	0x02108421, 0x42108421
};

template <>
inline int BitTools<unsigned long long>::builtinCounter(unsigned long long i) {
	return __builtin_popcountll(i);
}

template <>
inline int BitTools<unsigned long>::builtinCounter(unsigned long i) {
	return __builtin_popcountl(i);
}

template <>
inline int BitTools<unsigned int>::builtinCounter(unsigned int i) {
	return __builtin_popcount(i);
}

template <>
inline int BitTools<unsigned long long>::builtinLeast(unsigned long long w) {
	return __builtin_ffsll(w)-1;
}

template <>
inline int BitTools<unsigned long>::builtinLeast(unsigned long w) {
	return __builtin_ffsl(w)-1;
}

template <>
inline int BitTools<unsigned int>::builtinLeast(unsigned int w) {
	return __builtin_ffs(w)-1;
}

template <>
inline int BitTools<unsigned long long>::builtinNextLeast(unsigned long long w, int i) {
	return __builtin_ffsll(w & __mask[i + 1])-1;
}

template <>
inline int BitTools<unsigned long>::builtinNextLeast(unsigned long w, int i) {
	return __builtin_ffsl(w & __mask[i + 1])-1;
}

template <>
inline int BitTools<unsigned int>::builtinNextLeast(unsigned int w, int i) {
	return __builtin_ffs(w & __mask[i + 1])-1;
}

template <>
inline int BitTools<unsigned long long>::builtinMost(unsigned long long i) {
	return (sizeof(long long) << 3)-__builtin_clzll(i)-1;
}

template <>
inline int BitTools<unsigned long>::builtinMost(unsigned long i) {
	return (sizeof(long) << 3)-__builtin_clzl(i)-1;
}

template <>
inline int BitTools<unsigned int>::builtinMost(unsigned int i) {
	return (sizeof(int) << 3)-__builtin_clz(i)-1;
}

template <>
inline int BitTools<unsigned long long>::builtinNextMost(unsigned long long w, int i) {
	return __builtin_ffsll(w & ~__mask[i])-1;
}

template <>
inline int BitTools<unsigned long>::builtinNextMost(unsigned long w, int i) {
	return __builtin_ffsl(w & ~__mask[i])-1;
}

template <>
inline int BitTools<unsigned int>::builtinNextMost(unsigned int w, int i) {
	return __builtin_ffs(w & ~__mask[i])-1;
}

#endif /* BITTOOLS_H_ */
